package leetcode.year2021.month11;

import java.util.HashMap;

// 79. 单词搜索
public class _21_2Exist79 {
  //  深度优先搜索，遍历每个单词，如果遇到有符合条件的，就递归往里走
  public boolean exist(char[][] board, String word) {
    int m = board.length;
    int n = board[0].length;

    boolean[][] visited = new boolean[m][n];

    for (int i = 0; i < m; i++) {
      for (int j = 0; j < n; j++) {
        if (judgeDfs(0,board,i,j,word,visited)){
          return true;
        }
      }
    }
    return false;
  }

  private boolean judgeDfs(int i, char[][] board, int m, int n, String word,boolean[][] visited) {
    if (i == word.length()){
      return true;
    }
    if (m < 0 || m >= board.length || n < 0 || n >= board[0].length){
      return false;
    }
    if (visited[m][n] == true){
      return false;
    }
    visited[m][n] = true;
    if (board[m][n] == word.charAt(i)){
      boolean b = judgeDfs(i + 1, board, m + 1, n, word, visited) || judgeDfs(i + 1, board, m - 1, n, word, visited) || judgeDfs(i + 1, board, m, n + 1, word, visited) || judgeDfs(i + 1, board, m, n - 1, word, visited);
      visited[m][n] = false;
      return b;
    }
    visited[m][n] = false;
    return false;
  }

  /**
   * 给定一个 m x n 二维字符网格 board 和一个字符串单词 word 。如果 word 存在于网格中，返回 true ；否则，返回 false 。
   *
   * 单词必须按照字母顺序，通过相邻的单元格内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。
   *
   *  
   *
   * 示例 1：
   *
   *
   * 输入：board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCCED"
   * 输出：true
   * 示例 2：
   *
   *
   * 输入：board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "SEE"
   * 输出：true
   * 示例 3：
   *
   *
   * 输入：board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCB"
   * 输出：false
   *  
   *
   * 提示：
   *
   * m == board.length
   * n = board[i].length
   * 1 <= m, n <= 6
   * 1 <= word.length <= 15
   * board 和 word 仅由大小写英文字母组成
   *
   * 来源：力扣（LeetCode）
   * 链接：https://leetcode-cn.com/problems/word-search
   * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
   */
}
